from cmath import inf
from typing import List


class Solution:
    """
    方法：二分查找。在较短数组上二分查找，找到一个位置i，使得a[i]<=b[j+1] && b[j]<=a[i+1]，其中j=(m+n+1)/2-i。
    这样可以保证左半部分的数都小于等于右半部分的数。中位数就可以由左半部分的最大值和右半部分的最小值得到。

    Args:
        a: 第一个有序数组
        b: 第二个有序数组

    Returns:
        两个有序数组的中位数

    Time: O(log(min(m,n))) - m和n分别是两个数组的长度，在较短数组上二分查找

    Space: O(1) - 只使用常数额外空间
    """
    def findMedianSortedArrays(self, a: List[int], b: List[int]) -> float:
        if len(a) > len(b):
            a, b = b, a
        m, n = len(a), len(b)
        a = [-inf] + a + [inf]
        b = [-inf] + b + [inf]
        # 循环不变量 a[left] <= b[j+1]
        # 循环不变量 pythona[right] >= b[j+1]
        left , right = 0, m + 1
        while left + 1 < right: #[left, right]
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i
            if a[i] <= b[j+1]:
                left = i #[i, right]
            else:
                right = i #[left, i]
        i = left
        j = (m + n + 1) // 2 - i
        max1 = max(a[i], b[j])
        min2 = min(a[i+1], b[j+1])
        return max1 if(m + n) % 2 else (max1 + min2) / 2
    
    def findMedianSortedArrays1(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        totalLeft = (m + n + 1) / 2
        # nums1[i - 1] <= nums2[j] && nums2 [j-1] < = nums1[i]
        left, right = 0, m #[0, m]
        while left < right:
            i = left + (right - left + 1) / 2
            j = totalLeft - i
            if nums1[i - 1] > nums2[j]:
                #[left, i - 1]
                right = i - 1
            else:
                [i, right]
                left = i
        i = left
        j = totalLeft - i
        leftMax1 = nums1[i - 1] if i > 0 else float('-inf')
        leftMin1 = nums1[i] if i < m else float('inf')
        leftMax2 = nums2[j - 1] if j > 0 else float('-inf')
        leftMin2 = nums2[j] if j < n else float('inf')
        return max(leftMax1, leftMax2) if (m + n) % 2 == 1 else (max(leftMax1, leftMax2) + min(leftMin1, leftMin2)) / 2.0

    def test_findMedianSortedArrays(self):
        test_cases = [
            ([1, 3], [2], 2.0),
            ([1, 2], [3, 4], 2.5),
            ([0, 0], [0, 0], 0.0),
            ([], [1], 1.0),
            ([2], [], 2.0)
        ]
        
        for i, (a, b, expected) in enumerate(test_cases):
            result = self.findMedianSortedArrays(a, b)
            print(f"Test case {i + 1}: Input: a={a}, b={b} | Expected: {expected}, Got: {result}")

if __name__ == "__main__":
    solution = Solution()
    solution.test_findMedianSortedArrays()